package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?toCommentId=9147982
 * 来源：牛客网
 *
 * [编程题]对称的二叉树
 * 热度指数：340041时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
 * 示例1
 * 输入
 * {8,6,6,5,7,7,5}
 * 输出
 * true
 * 示例2
 * 输入
 * {8,6,9,5,7,7,5}
 * 输出
 * false
 */
public class SymmetricalBinaryTree {

    ArrayList<Integer> preorder = new ArrayList<>(); //使用类似前序遍历得到的顺序
    ArrayList<Integer> SymmetricalPreorder = new ArrayList<>(); //使用对称的类似前序遍历（先节点本身再右子节点再左子节点）

    @Test
    public void test() {
        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(2);
        TreeNode treeNode7 = new TreeNode(2);
        TreeNode treeNode8 = new TreeNode(1);
        TreeNode treeNode9 = new TreeNode(1);

        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode3.right = treeNode5;
        treeNode4.left = treeNode6;
        treeNode5.right = treeNode7;
        treeNode6.left = treeNode8;
        treeNode7.right = treeNode9;

        System.out.println(isSymmetrical(treeNode));
        System.out.println(preorder);
        System.out.println(SymmetricalPreorder);
    }

    boolean isSymmetrical(TreeNode pRoot) {

        if (pRoot == null) {
            return true;
        }

        preorderTransversal(pRoot);
        SymmetricalPreorderTransversal(pRoot);

        // 如果两个集合不是一模一样的顺序，那就返回false
        for (int i = 0; i < preorder.size(); i++) {
            /*
             * 需要注意的是integer的比较大小的问题：
             * integer -128 ~ 127 是同一地址值   这个取值范围之外就不能用 == 比较大小了
             * 所以我使用了equals方法
             */
            if (!preorder.get(i).equals(SymmetricalPreorder.get(i))) {
                return false;
            }
        }

        return true;
    }

    private void SymmetricalPreorderTransversal(TreeNode treeNode) {
        if (treeNode==null){
            SymmetricalPreorder.add(Integer.MIN_VALUE);
            return;
        }else {
            SymmetricalPreorder.add(treeNode.val);
        }

        if (treeNode.left!=null||treeNode.right!=null) {
            SymmetricalPreorderTransversal(treeNode.right);
            SymmetricalPreorderTransversal(treeNode.left);
        }
    }

    private void preorderTransversal(TreeNode treeNode) {
        if (treeNode==null){
            preorder.add(Integer.MIN_VALUE);
            return;
        }else {
            preorder.add(treeNode.val);
        }

        if (treeNode.left!=null||treeNode.right!=null) {
            preorderTransversal(treeNode.left);
            preorderTransversal(treeNode.right);
        }
    }
}
